package com.yuufa.graph;

public class ShortestPath {

    public static void main(String[] args) {
        int n = 8;
        int[] dist = new int[n + 1];
        int[] pred = new int[n + 1];
        int[][] cost = new int[n + 1][n + 1];
        int[] s = new int[n + 1];

        initial(n, cost);

        shortestPath(5, cost, dist, n, pred, s);

        for (int i = 1; i <= n; i++) {
            System.out.print(dist[i] + ",");
        }
        System.out.println();
        for (int i = 1; i <= n; i++) {
            System.out.print(pred[i] + ",");
        }
        
    }

    public static void shortestPath(int v, int[][] cost, int[] dist, int n, int[] pred, int[] s) {

        for (int i = 1; i <= n; i++) {
            s[i] = 0;
            dist[i] = cost[v][i];
            if (cost[v][i] != Integer.MAX_VALUE) {
                pred[i] = v;
            } else {
                pred[i] = 0;
            }
        }

        s[v] = 1;
        dist[v] = 0;
        pred[v] = 0;

        int num = 2;
        int vertextNum;

        while (num <= n) {
            vertextNum = getShortestDistVertexNum(dist,s, n);
            s[vertextNum] = 1;
            num += 1;
            
            for (int i = 1; i <= n; i++) {
                if (cost[vertextNum][i] != Integer.MAX_VALUE) {
                    if (s[i] == 0) {
                        if (dist[vertextNum] + cost[vertextNum][i] < dist[i]) {
                            pred[i] = vertextNum;
                            dist[i] = dist[vertextNum] + cost[vertextNum][i];
                        }
                    }
                }
            }
            
        }
        
    }

    public static int getShortestDistVertexNum(int[] dist, int[] s, int n) {
        int tmp = Integer.MAX_VALUE;
        int num = 0;

        for (int i = 1; i <= n; i++) {
            if (dist[i] != Integer.MAX_VALUE) {
                if (s[i] == 0) {
                    if (dist[i] < tmp) {
                        tmp = dist[i];
                        num = i;
                    }
                }
            }
        }

        return num;
    }

    public static void initial(int n, int[][] cost) {
        for (int i = 1; i <= n; i++) {
            for(int j=1;j<=n;j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

        cost[2][1] = 300;
        cost[3][1] = 1000;
        cost[3][2] = 800;
        cost[4][3] = 1200;
        cost[5][4] = 1500;
        cost[5][6] = 250;
        cost[6][4] = 1000;
        cost[6][7] = 900;
        cost[6][8] = 1400;
        cost[7][8] = 1000;
        cost[8][1] = 1700;
    }
}
